package com.learn.algorithm_121;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * 121. 买卖股票的最佳时机
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
 * @author gatts, 2022/1/12 20:00
 */
public class BestSellTime {

    @Test
    public void test() {
        int[] arr = {7,1,5,3,6,4};
        System.out.println(maxProfit(arr));
    }

    /**
     * 1. 计算今天之前的最低价格
     * 2. 计算今天卖出的利润，并记录
     * 3. 比较利润，得出最大值
     *
     * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/comments/
     */
    public int maxProfit(int[] prices) {
        // 至少要有两天才能卖出
        if (prices == null || prices.length <= 1) {
            return 0;
        }

        Map<String, Integer> map = new HashMap<>();

        int buy = prices[0];
        int profit = 0;
        map.put("buy", 1);
        map.put("sell", 2);

        // 第二天开始
        for (int i = 1; i < prices.length; i++) {
            // 记录第几天买、卖
            if (prices[i] == Math.min(buy, prices[i])) {
                // 更新买入时机
                map.put("buy", i+1);
            }

            // 计算今天卖出利润
            int currentProfit = prices[i] - buy;

            if (currentProfit == Math.max(currentProfit, profit)) {
                map.put("sell", i+1);
            }

            // 计算目前最小买入价
            buy = Math.min(buy, prices[i]);
            // 计算目前最大利润
            profit = Math.max(currentProfit, profit);
        }
        System.out.println(map);
        return profit;
    }

}
